The LP relaxation of the original problem is
\begin{align}
 z^{LP} = \max \quad \vc{c}' \vc{x} & \\
 \vc{A}^1 \vc{x} & \le \vc{b}^1 \\
 \vc{A}^2 \vc{x} & \le \vc{b}^2 \\
 \vc{x} & \in \R^n_{\geq 0}
\end{align}

The Lagrangian relaxation of the reformulation IP($\vc{u}$) after dualizing constraints~\eqref{eq:lag-decomp} is
\begin{align}
	z(\vc{u}) = \max \quad \alpha \vc{c}' \vc{x} + (1-\alpha)\vc{c}' \vc{y} + \vc{u}'(\vc{x}-\vc{y}) & \\
	\vc{A}^1 \vc{x} & \le \vc{b}^1 \\
	\vc{A}^2 \vc{y} & \le \vc{b}^2 \\
	\vc{x}, \vc{y} & \in \Z^n_{\ge 0}
\end{align}

The LD problem is to solve $w_{\LD} = \min_{\vc{u}} z(\vc{u})$. In what follows, we prove that $w_{\LD} = z^{LP}$.

Choose a finite set of elements
\begin{equation}
X' = \left\{ (\vc{x}^1,\vc{y}^1), \ldots, (\vc{x}^T,\vc{y}^T) \right\} \subseteq X = \left\{(\vc{x},\vc{y}) : \vc{x}, \vc{y} \in \Z^n_{\ge 0}, \vc{A}^1 \vc{x} \le \vc{b}^1, \vc{A}^2 \vc{y} \le \vc{b}^2  \right\}. \label{ex7:defofX}
\end{equation}

We define the following linear program, which is a restriction of the LD problem to the set $X'$:

\begin{align}
	w_{\LD}'(X') = \min_{\vc{u}, \eta} \eta & \\
	\eta & \ge \alpha \vc{c}' \vc{x}^t + (1-\alpha) \vc{c}' \vc{y}^t + \vc{u}'(\vc{x}^t - \vc{y}^t) & \forall t \in \{1,\ldots,T\} \label{ex7:etamax} \\
	\vc{u}, \eta & \quad \mathrm{unrestricted}
\end{align}

We rewrite constraint~\eqref{ex7:etamax} in matrix form, where subscripts denote components of vectors:

\begin{equation}
	\begin{pmatrix}
		1 & (\vc{y}^1-\vc{x}^1)_1 & \cdots & (\vc{y}^1-\vc{x}^1)_T \\
		\vdots & \vdots & \ddots & \vdots \\
		1 & (\vc{y}^T-\vc{x}^T)_1 & \cdots & (\vc{y}^T-\vc{x}^T)_T 
	\end{pmatrix}
	\begin{pmatrix}
		\eta \\
		u_1 \\
		\vdots \\
		u_T
	\end{pmatrix}
	=
	\begin{pmatrix}
		\alpha \vc{c}' \vc{x}^1+(1-\alpha) \vc{c}' \vc{y}^1 \\
		\vdots \\
		\alpha \vc{c}' \vc{x}^T+(1-\alpha) \vc{c}' \vc{y}^T
	\end{pmatrix}
\end{equation}

Now we can easily read off the (strong) dual of the linear program:
\begin{align}
	w_{\LD}'(X') = \max_{\vc{\mu}} \quad \sum_{t=1}^T \left( \alpha \vc{c}' \vc{x}^t + (1-\alpha) \vc{c}' \vc{y}^t\right) \mu_t & \\
	\mu_t & \ge 0 & \forall t \in \{1,\ldots,T\} \label{ex7:convex1} \\
	\sum_{t=1}^T \mu_t &= 1 \label{ex7:convex2} \\
	\sum_{i=1}^T \left( \vc{y}^i - \vc{x}^i \right)_t \mu_i &= 0 & \forall t \in \{1,\ldots,T\}
\end{align}

Constraints \eqref{ex7:convex1} and~\eqref{ex7:convex2} ensure that $\vc{x}=\sum_{t=1}^T \mu_t \vc{x}^t$ and $\vc{y}=\sum_{t=1}^T \mu_t \vc{y}^t$ are convex combinations in the first and second entries of the elements of $X'$. If we consider these substitutions, we can rewrite $w_{\LD}'$ as
\begin{align}
	w_{\LD}'(X') = \max_{\vc{x},\vc{y}} \quad \alpha \vc{c}' \vc{x} + (1-\alpha) \vc{c}' \vc{y} & \\
	(\vc{y}-\vc{x})_t &= 0 & \forall t \in \{1,\ldots,T\} \label{ex7:xisy} \\
	\vc{x} & \in \conv \left( \left\{ \vc{v} : (\vc{v},\cdot) \in X' \right\} \right) \\
	\vc{y} & \in \conv \left( \left\{ \vc{w} : (\cdot,\vc{w}) \in X' \right\} \right)
\end{align}

By the definition of the convex hull of an infinite set we see that:
\begin{equation}
	w_{\LD} = \max_{\substack{X' \subset X \\ X' \; \mathrm{finite}}} \quad w_{\LD}'(X').
\end{equation}

From constraint~\eqref{ex7:xisy}, we can reformulate $w_{\LD}$ as follows:
\begin{align}
	w_{\LD} = \max_{\vc{x}} \quad \vc{c}' \vc{x} & \\
	\vc{x} & \in \conv \left(  \left\{ \vc{z} \in \Z^n_{\ge 0} : \vc{A}^1 \vc{z} \le \vc{b}^1 \right\} \right) \cap \conv \left(  \left\{ \vc{z} \in \Z^n_{\ge 0} : \vc{A}^2 \vc{z} \le \vc{b}^2 \right\} \right) \label{ex7:convex3}
\end{align}

By linearity of matrix multiplication, we find that $\vc{A}^1 \vc{x} \le \vc{b}^1$ and $\vc{A}^2 \vc{x} \le \vc{b}^2$ from constraint~\eqref{ex7:convex3}.

This shows that $w_{\LD} \le z^{\LP}$ since every solution to the LD problem is a solution to the LP relaxation of the original formulation. Equality does not hold in general, e.g.\ $x_1 + x_2 \le 0.5$ has only one solution for the LD but several solutions to the LP relaxation.

In general, $z = w_{\LD}$ does not hold either because the intersection of the convex hull of two point sets can be a real superset of the convex hull of the intersection of the two point sets.

